 // 674. 最长连续递增序列
 const numslc = [1,3,5,4,7];
 function findLengthOfLCIS (nums) {
   let dp = Array(nums.length).fill(1);
   let res = 1;

   for (let i = 0; i < nums.length - 1; i++) {
     if (nums[i + 1] > nums[i]) {
       dp[i + 1] = dp[i] + 1;
     }
     res = Math.max(res, dp[i + 1]);
   }
   return res;
 }
 console.log(findLengthOfLCIS(numslc));

 // 22. 零钱兑换
 const coins = [1, 2, 5], amount = 11;
//  function coinChange(coins, amount) {
//     let dp = Array(amount + 1).fill(Infinity);
//     dp[0] = 0;
//     for(let i = 0; i <= dp.length - 1; i++) {
//       for(let v of coins) {
//         if (i - v < 0 ) {
//           continue;
//         }
//         dp[i] = Math.min(dp[i], dp[i - v] + 1);
//       }
//     }

//     return dp[amount] == amount + 1 ? -1 : dp[amount];
//   }

const coinChange = (coins, amount) => {
    if(!amount) {
        return 0;
    }

    let dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for(let i =0; i < coins.length; i++) {
        for(let j = coins[i]; j <= amount; j++) {
            dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange(coins, amount));

// 718. 最长重复子数组
// dp[i][j]为A数组下的当前i位置的值和B数组下的j位置的值，当前公共字符串的长度
const A = [1,2,3,2,1],B = [3,2,1,4,7];
function findLength(a1, a2) {
    let dp = Array(a1.length + 1).fill(Array(a2.length + 1).fill(0));
    let res = 0;
    for (let i = 1; i < a1.length + 1; i++ ) {
        for (let j = 1; j < a2.length + 1; j++) {
            if (a1[i - 1] == a2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
      
            res = Math.max(dp[i][j], res);
        }
    }

    return res;
}
console.log(findLength(A, B))

// 300.最长递增子序列
// dp[i], 第i个位置的最长递增子序列，由dp[j]决定，前提是nums[i] > nums[j], j为已经遍历过的元素位置;
const nums1 = [10,9,2,5,3,7,101,18];

function lengthOfLIS(nums) {
    let dp = Array(nums.length).fill(1);
    let res = 1;
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++)
        if (nums[i] > nums[j]) {
            dp[i] = dp[j] + 1;
        }
        
        res = Math.max(res, dp[i]);
    }
    return res;
}
console.log(lengthOfLIS(nums1))


